package offer.day35;

import java.util.Arrays;

public class No61IsContinuous {
    /*
     * 面试题61：扑克牌中的顺子
     * 题目：从扑克牌中随机抽抽出5张牌，判断是不是一个顺子，
     * 即这5张牌是不是连续的。
     * 2~10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字
     *
     * 思路：
     * 1>首先对数组进行排序
     * 2>计算出0的个数
     * 3>计算出数与数之间的间隔数  其中若两个值相等 ，即含有对子，则一定是不连续的
     * 判断间隔数是否大于o的个数 若大于 则不连续 否则连续
     *
     * 这里排序算法使用的是java自带的Arrays.sort函数，不必考虑时间复杂度的问题
     * 这是因为：通常认为不同级别的时间复杂度只有当n足够大的时候才是有意义的
     * 本题中数组的长度固定，只有五张牌，所以时间复杂度上不会有太大的区别，
     * 所以使用简洁易懂的方法来实现算法就可以
     *
     *
     * */
    public static void main(String[] args) {
        No61IsContinuous c = new No61IsContinuous();
        int[] numbers = {1,3,0,0,5};
        if(c.IsContinuous(numbers))
            System.out.println("随机抽取的这五张扑克牌是顺子！");
        else
            System.out.println("随机抽取的这五张扑克牌不是顺子！！");
    }

    private boolean IsContinuous(int[] numbers) {
        if(numbers==null||numbers.length==0) return false;
        Arrays.sort(numbers);
        int numberOf0=0;
        int numberOfGap=0;
        for(int i=0;i<numbers.length&&numbers[i]==0;i++){
            numberOf0++;
        }
        int small=numberOf0;
        int big=small+1;
        while(big<numbers.length){
            if(numbers[small]==numbers[big]){
                return false;
            }
            numberOfGap +=numbers[big++]-numbers[small++]-1;
        }
        return numberOfGap<=numberOf0;
    }
}
